백준 11689번
오늘 풀어본 문제는 백준의 11689번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
자연수 $n$ 이 주어졌을 때, $\text{GCD}(n, k) = 1$ 을 만족하는 자연수 $1 \le k \le n$ 의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 $n$ $(1 \le n \le 10^{12})$이 주어진다.
출력
$\text{GCD}(n, k) = 1$ 을 만족하는 자연수 $1 \le k \le n$ 의 개수를 출력한다.
풀이과정
(사실상) 1번째 시도
문제를 보고 오일러 피 함수를 구현해야 하는 문제라는 것을 알 수 있었다.
그냥 단순하게 모든 수에 대해서 일일히 std::gcd 함수를 써서 $1$ 이 되는지 확인하면 당연히 시간초과가 날 것이기 때문에, 오일러 피 함수의 성질을 활용하여 구현해야 함을 알 수 있었다.
오일러 피 함수는 다음과 같은 성질이 성립한다.
-
어떤 소수의 제곱수 $p^k$ 에 대하여 들어오면 $\phi(p^k) = p^{k-1}(p-1)$ 이다.
-
서로소인 $n$, $m$ 에 대하여 $\phi(nm) = \phi(n)\phi(m)$ 이다.
이러한 점을 이용하여 나는 입력 받은 수를 소인수분해하여 이 성질들을 이용하기로 했고, 지난 문제에서 만들어둔 폴라드 로 알고리즘 코드를 그대로 이용하였다.
코드는 다음과 같이 작성하였다. 제출할 때는 헤더파일의 코드를 붙여넣어 제출하였다.
(위에 ‘사실상’ 1번째 시도라고 쓴 이유는, 원래는 메인 함수의 변수 n 을 int 형으로 선언하여 코드를 제출했었는데 범위가 더 큰 똑같은 문제에도 코드를 그대로 쓰기 위해 unsigned long long int 형으로 바꿔서 한 번 더 내려다가 헤더파일을 붙여넣는 것을 깜빡해서 ‘컴파일 에러’ 를 받았고, 3번째 제출에서 제대로 붙여넣어 다시 한 번 ‘맞았습니다’ 를 받았기 때문이다.)
custom_algorithms.hpp
#ifndef __CUSTOM_ALGORITHMS_HPP__
#define __CUSTOM_ALGORITHMS_HPP__
#include <cmath>
#include <vector>
#include <complex>
#include <string>
#include <random>
#include <numeric>
namespace custom_algorithms {
namespace fft {
long double const_pi(void) {
return std::atan(1) * 4;
}
void FFT(std::vector<std::complex<long double>>& a, const std::complex<long double>& w) {
size_t n = a.size();
if (n == 1) {
return;
}
std::vector<std::complex<long double>> a_even(n/2), a_odd(n/2);
for (size_t i=0; i<(n/2); i++) {
a_even[i] = a[2 * i];
a_odd[i] = a[2 * i + 1];
}
std::complex<long double> w_squared = w * w;
FFT(a_even, w_squared);
FFT(a_odd, w_squared);
std::complex<long double> w_i = 1;
for (size_t i=0; i<(n/2); i++) {
a[i] = a_even[i] + w_i * a_odd[i];
a[i + (n/2)] = a_even[i] - w_i * a_odd[i];
w_i *= w;
}
}
std::vector<std::complex<long double>> convolution(std::vector<std::complex<long double>> a, std::vector<std::complex<long double>> b, bool getIntegerResult = false) {
size_t n = 1;
long double pi = const_pi();
while (n <= a.size() || n <= b.size()) {
n <<= 1;
}
n <<= 1;
a.resize(n);
b.resize(n);
std::vector<std::complex<long double>> c(n);
std::complex<long double> w(cos(2 * pi / n), sin(2 * pi / n));
FFT(a, w);
FFT(b, w);
for (int i = 0; i < n; i++) {
c[i] = a[i] * b[i];
}
FFT(c, std::complex<long double>(w.real(), -w.imag()));
for (int i = 0; i < n; i++) {
c[i] /= std::complex<long double>(n, 0);
if (getIntegerResult) {
c[i] = std::complex<long double>(round(c[i].real()), round(c[i].imag()));
}
}
return c;
}
template <typename T>
std::vector<T> stringToVector(const std::string& str) {
std::vector<T> result(str.size());
for (size_t i=0; i<str.size(); i++) {
result[i] = static_cast<T>(str[i] - '0');
}
return result;
}
template <typename T>
std::string vectorToString(const std::vector<T>& vec) {
for (size_t i=vec.size()-1; i>0; i--) {
vec[i-1] += (vec[i] / 10);
vec[i] %= 10;
}
std::string result;
for (auto& digit : vec) {
result += static_cast<char>(digit + '0');
}
return result;
}
template <typename T>
std::string fastMultiplication(const T& A, const T& B) {
return fastMultiplication(std::to_string(A), std::to_string(B));
}
template <>
std::string fastMultiplication(const std::string& A, const std::string& B) {
std::vector<int> a = stringToVector<int>(A);
std::vector<int> b = stringToVector<int>(B);
size_t n = a.size() + b.size() - 1;
std::vector<std::complex<long double>> a_complex(a.begin(), a.end());
std::vector<std::complex<long double>> b_complex(b.begin(), b.end());
std::vector<std::complex<long double>> conv = convolution(a_complex, b_complex, true);
std::vector<int> digitArray(n, 0);
for (size_t i=0; i<n; i++) {
digitArray[i] = static_cast<int>(conv[i].real());
}
for (int i=digitArray.size()-1; i>0; i--) {
digitArray[i-1] += (digitArray[i] / 10);
digitArray[i] %= 10;
}
std::string result;
for (auto& digit : digitArray) {
result += std::to_string(digit);
}
return result;
}
}
namespace common {
template <typename T>
T stoiWithMOD(const std::string& s, const T& MOD=static_cast<T>(0)) {
T result = static_cast<T>(0);
for (auto& c : s) {
result *= 2;
if (MOD != 0) {
result %= MOD;
}
T temp = result;
temp *= 2;
if (MOD != 0) {
temp %= MOD;
}
temp *= 2;
if (MOD != 0) {
temp %= MOD;
}
result += temp;
if (MOD != 0) {
result %= MOD;
}
T added = static_cast<T>(c - '0');
if (MOD != 0) {
added %= MOD;
}
result += added;
if (MOD != 0) {
result %= MOD;
}
}
return result;
}
template <typename T>
T multWithMOD_int128(const T& a, const T& b, const T& MOD=static_cast<T>(0)) {
__int128 result = a;
result *= static_cast<__int128>(b);
if (MOD != 0) {
result %= MOD;
}
return result;
}
template <typename T>
T power(const T& a, const T& b, const T& MOD=static_cast<T>(0), bool useInt128 = true){
T result = static_cast<T>(1);
std::string (*mult)(const T&, const T&) = fft::fastMultiplication<T>;
T base = a;
T exponent = b;
if (MOD != 0) {
base %= MOD;
}
while (exponent) {
if (exponent % 2 == 1) {
if (!useInt128) {
result = stoiWithMOD(mult(result, base), MOD);
}
else {
result = multWithMOD_int128(result, base, MOD);
}
}
if (!useInt128) {
base = stoiWithMOD(mult(base, base), MOD);
}
else {
base = multWithMOD_int128(base, base, MOD);
}
exponent >>= 1;
}
return result;
}
}
namespace miller_rabin {
std::vector<int> basicPrimes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
bool isComposite(unsigned long long int a, unsigned long long int n, bool useInt128 = true) {
unsigned long long int k = n - 1;
while (true) {
unsigned long long int d = common::power(a, k, n, useInt128);
if (k % 2 == 1) {
return (d != 1 && d != n - 1);
}
else if (d == n - 1) {
return false;
}
k /= 2;
}
}
bool isPrime(unsigned long long int n, bool useInt128 = true) {
if (n <= 1) {
return false;
}
for (auto& prime : basicPrimes){
if (n == prime) {
return true;
}
else if (n % prime == 0) {
return false;
}
}
for (auto& prime : basicPrimes) {
if (isComposite(prime, n, useInt128)) {
return false;
}
}
return true;
}
}
namespace pollard_rho {
unsigned long long int findFactor(unsigned long long int n, bool useInt128 = true) {
static std::mt19937_64 mt(std::random_device{}());
static std::uniform_int_distribution<unsigned long long int> dist1(2, n);
static std::uniform_int_distribution<unsigned long long int> dist2(1, n);
std::string (*mult)(const unsigned long long int&, const unsigned long long int&) = fft::fastMultiplication<unsigned long long int>;
if (n == 1) {
return 1;
}
else if (n % 2 == 0) {
return 2;
}
else if (miller_rabin::isPrime(n)) {
return n;
}
else {
unsigned long long int x = dist1(mt);
unsigned long long int y = x;
unsigned long long int c = dist2(mt);
unsigned long long int d = 1;
while (d == 1) {
if (!useInt128) {
x = (common::stoiWithMOD(mult(x, x), n) + c) % n;
y = (common::stoiWithMOD(mult(y, y), n) + c) % n;
y = (common::stoiWithMOD(mult(y, y), n) + c) % n;
}
else {
x = common::multWithMOD_int128(x, x, n) + c;
y = common::multWithMOD_int128(y, y, n) + c;
y = common::multWithMOD_int128(y, y, n) + c;
}
d = std::gcd(n, (x > y ? x - y : y - x));
if (d == n) {
return findFactor(n);
}
}
if (miller_rabin::isPrime(d, useInt128)) {
return d;
}
else {
return findFactor(d);
}
}
}
std::vector<std::pair<unsigned long long int, unsigned long long int>> factorize(unsigned long long int n, bool useInt128 = true) {
std::vector<std::pair<unsigned long long int, unsigned long long int>> result;
struct cmp {
bool operator()(const std::pair<unsigned long long int, unsigned long long int>& a, const std::pair<unsigned long long int, unsigned long long int>& b) {
return a.first < b.first;
}
};
while (n > 1) {
unsigned long long int factor = findFactor(n, useInt128);
n /= factor;
result.emplace_back(std::make_pair(factor, 1));
while (n % factor == 0) {
n /= factor;
result.back().second++;
}
}
std::sort(result.begin(), result.end(), cmp());
return result;
}
}
namespace euler_totient {
unsigned long long int phi(unsigned long long int n) {
unsigned long long int result = 1;
auto factors = pollard_rho::factorize(n);
for (auto& [factor, power] : factors) {
result *= common::power(factor, power-1) * (factor-1);
}
return result;
}
}
namespace floyd_warshall {
template <template<typename, typename> typename Table, typename Node, typename Distance>
Table<Node, Table<Node, Distance>> getShortestPath(const Table<Node, Table<Node, Distance>>& graph) {
Table<Node, Table<Node, Distance>> distance = graph;
for (auto [middle, _] : distance) {
for (auto [start, _] : distance) {
for (auto [end, _] : distance) {
if (distance[start][end] > distance[start][middle] + distance[middle][end]) {
distance[start][end] = distance[start][middle] + distance[middle][end];
}
}
}
}
return distance;
}
}
}
#endif // __CUSTOM_ALGORITHMS_HPP__
main.hpp
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
using namespace custom_algorithms;
using ll = long long int;
using ull = unsigned long long int;
using pll = pair<ll, ll>;
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ull n;
cin >> n;
cout << euler_totient::phi(n);
return 0;
}
그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.
마무리
사실 이 문제는 소인수분해를 하는데 있어 폴라드 로 함수까지 쓸 필요는 없긴 했지만, 나중에 그래야 하는 문제가 있다는 걸 알고있었기 때문에 지난 문제에서 고생해가며 구현해 두었다.
그리고 이 코드를 그대로 가져다가 입력받는 수의 범위가 더 큰 백준 13926번 문제를 풀 수 있었다! 문제의 난이도 티어는 오늘 기준 Diamond V 문제이다. 드디어 다이아 문제를 하나 풀어내는 데 성공한 것이다!
힘든거 하나 만들었으니 앞으로 세그먼트 트리처럼 두고두고 우려먹을 수 있으면 좋겠다…
내가 만든 알고리즘 헤더파일은 내 레포지토리2에서 확인할 수 있다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/11689
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C%2B%2B/custom_algorithms.hpp